# !/usr/usuari/des python
#  -*- coding: utf-8 -*-
"""
@Author        : itgnay
@Time          : 2022/12/22 20:06
@FileName      : 插入排序.py
@LastEditors   : None
@Editors       : PyCharm
"""


# 稳定

def insertion_sort(arr):
    # 遍历未排序部分
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1

        # 将元素插入到已排序部分
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key

    return arr


# 示例用法
arr = [14, 33, 27, 10, 35, 19, 42, 44]
sorted_arr = insertion_sort(arr)
print("排序后的数组：", sorted_arr)
